package com.xzz.treeBST;

/**
 * @author: hhz
 * @create: 2021-12-21 13:21
 * 96. 不同的二叉搜索树
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 **/
public class NumTrees {
    public static void main(String[] args) {
        System.out.println(numTrees(17));
    }

    static int[] memo;

    public static int numTrees(int n) {
        //构建备忘录
        memo = new int[n + 1];
        return count(1, n);
    }

    public static int count(int start, int end) {
        if (start > end) {
            return 1;
        }
        if (memo[end - start] != 0) {
            return memo[end - start];
        }

        int num = 0;
        //以i为根节点 i左边作为左子树 i右边作为右子树
        for (int i = start; i <= end; i++) {
            int left = count(start, i - 1);
            int right = count(i + 1, end);
            num += left * right;
        }
        memo[end - start] = num;
        return num;
    }
}
